package weekMatch.one_346;

public class LeeCode_03 {
    public static void main(String[] args) {
        System.out.println(punishmentNumber(10));
    }
    private static int punishmentNumber(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (dfs(i * i + "", i, 0, 0)){
                ans += i * i;
            }
        }
        return ans;
    }
    private static boolean dfs(String s, int goal, int index, int sum){
        int n = s.length(), r = index + 1;
        if (r > n){
            return sum == goal;
        }
        while (r <= n){
            String son = s.substring(index, r);
            int num = Integer.parseInt(son);
            int newS = sum + num;
            if (newS <= goal && dfs(s, goal, r, newS)) {
                return true;
            }
            r++;
        }
        return false;
    }
}
